
Après sa défaite dans le premier Star Fox, Andross revient dans la galaxie de Lylat et lance une attaque contre Corneria, en utilisant sa nouvelle flotte de cuirassés et de missiles géants lancés à partir de bases sur des planètes pour détruire Corneria. Le général Pepper appelle de nouveau l'équipe Star Fox pour obtenir de l'aide. Armée de nouveaux Arwings, d'un Mothership et de deux nouvelles recrues (Miyu, un lynx, et Fay, un chien), l'équipe Star Fox doit défendre Corneria avant qu'Andross n'utilise ses forces pour infliger des dommages critiques à Corneria. En cours de route, Star Fox doit aussi lutter contre des ennemis, des cuirassés d'Andross menaçant la planète Corneria, les membres de l'équipe Star Wolf, et enfin Andross lui-même.